package demo1;

public class DynamicPlanning {
    /**
     * 动态规划 笔记+习题*/

    /**
     * 求最小花费
     * 时间复杂度O（n）
     * 空间复杂度O（n）
     * 状态表示dp[i] 代表从起点到达i级台阶所花费的最小体力值*/
    public int minCostClimbingStairs(int[] cost) {
        //创建dp表
        int[] dp = new int[cost.length+1];

        //因为数组若是不进行赋值，其本身就为0，故不对其进行初始化
        for(int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

    /**
     * 求最小花费
     * 时间复杂度O（n）
     * 空间复杂度O（n）
     * 状态表示dp[i] 代表从i级台阶到达楼顶的最小花费*/
    public int minCostClimbingStairsOther(int[] cost) {
        //1 创建dp表
        int n = cost.length;
        int[] dp = new int[n];
        //2 初始化
        dp[n-1] = cost[n-1]; dp[n-2] = cost[n-2];
        for(int i = (n-3); i >= 0; i--) {
            //3 状态转移方程
            dp[i] = Math.min(dp[i+1],dp[i+2])+cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }

    /**
     * 解码方式
     * 时间复杂度O（n）
     * 空间复杂度O（n）
     * */
    public int numDecodings(String s) {
        //处理边界情况
        if(s.length()==1) {
            if(s.charAt(0)=='0') {
                return 0;
            } else {
                return 1;
            }
        }

        //1 创建dp表
        int[] dp = new int[s.length()];

        //2 初始化
        if(s.charAt(0)>='1' && s.charAt(0)<='9') {
            dp[0] = 1;
            if(s.charAt(1)>='1' && s.charAt(1)<='9') {
                dp[1] = 1;
            } else {
                dp[1] = 0;
            }
        } else {
            dp[0] = 0;
        }
        int num = (s.charAt(0)-48)*10 + (s.charAt(1)-48);
        if(num>=10 && num<=26) {
            dp[1]+=1;
        }

        for(int i = 2; i < dp.length; i++) {
            //3 状态转移方程
            int one = 0;
            if(s.charAt(i)>='1' && s.charAt(i)<='9') {
                one = dp[i-1];
            } else {
                one = 0;
            }
            int two = 0;
            num = (s.charAt(i-1)-48)*10 + (s.charAt(i)-48);
            if(num>=10 && num<=26) {
                two = dp[i-2];
            } else {
                two = 0;
            }
            if(one == 0 && two == 0) {
                return 0;
            }
            dp[i] = one + two;
        }
        return dp[dp.length-1];
    }

    /**
     * 解码方式
     * 时间复杂度O（n）
     * 空间复杂度O（n）
     * 代码结构优化*/
    public int numDecodingsOther(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        int[] dp = new int[n];

        //2 初始化
        if(chars[0] != '0') dp[0] = 1;
        //处理边界情况
        if(chars.length==1) return dp[0];
        if(chars[1] != '0' && chars[0] != '0') dp[1]+=1;
        int tmp = (chars[0]-'0')*10 + (chars[1]-'0');
        if(tmp >= 10 && tmp <= 26) dp[1]+=1;

        for(int i = 2; i < n; i++) {
            //3 状态转移方程
            if(chars[i]!='0') dp[i]+=dp[i-1];
            tmp = (chars[i-1]-'0')*10 + (chars[i]-'0');
            if(tmp >= 10 && tmp <= 26) dp[i]+=dp[i-2];
            if(dp[i]==0) return 0;
        }
        return dp[n-1];
    }

    /**
     * 不同路径
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）
     * */
    public int uniquePaths(int m, int n) {
        //1 创建dp表-->使用虚拟位置的方法进行初始化，故行列多开辟1
        //dp[1][1]为原始起点
        int[][] dp = new int[m+1][n+1];

        //2 初始化
        dp[0][1] = 1;

        //3 填表-->从上到下 从左到右
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                //4 状态转移方程
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        //5 返回
        return dp[m][n];
    }

}
